package simple;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Random;

/**
 * @author cmqzyd0700@163.com
 * @version 1.0
 * @since 2020/7/6 22:37
 */
public class No169_多数元素 {
    public static void main(String[] args) {
        Solution169 solution169 = new Solution169();
        int[] nums = new int[]{2, 2, 6, 2, 2, 6, 3, 2};
        int majorityElement = solution169.majorityElement(nums);
        System.out.println(majorityElement);
    }
}

class Solution169 {
    public int majorityElement(int[] nums) {
        //终极杀手锏,2行代码
        Arrays.sort(nums);
        return nums[nums.length / 2];
    }
}

    //public int majorityElement(int[] nums) {
    //    //投票法,非目标数-1,目标数+1
    //    int check = nums[0]; //2
    //    int count = 0;
    //    for (int num : nums) {
    //        if (count == 0) {
    //            //换
    //            check = num;
    //        }
    //        if (check == num) {
    //            count++;
    //        } else {
    //            count--;
    //        }
    //    }
    //    return check;
    //}


    //public int majorityElement(int[] nums) {
    //    //机智地赖皮
    //    //累死计算机
    //    while (true) {
    //        //[0,nums.length) 区间内进行随机
    //        int random = (int) (Math.random() * nums.length);
    //        //记录出现的次数
    //        int count = 0;
    //        for (int num : nums) { //最多31次,几率1/21亿!!!!!
    //            if (nums[random] == num) {
    //                count++;
    //            }
    //            if (count > nums.length / 2) {
    //                return nums[random];
    //            }
    //        }
    //    }
    //}


    //public int majorityElement(int[] nums) {
    //    //哈希
    //    //(2,3)(6,2)(3,1) 直接返回最大
    //    Map<Integer, Integer> map = new HashMap<>();
    //    for (int num : nums) {
    //        //初始化
    //        addMapKeys(map, num);
    //    }
    //
    //    int max = 0;
    //    int res = 0;
    //    //map循环
    //    for (Map.Entry<Integer, Integer> data : map.entrySet()) {
    //        //出现的次数
    //        int value = data.getValue();
    //        max = Math.max(max, value);
    //        if (max == value) {
    //            res = data.getKey();
    //        }
    //    }
    //    return res;
    //}
    //
    //public void addMapKeys(Map<Integer, Integer> map, int key) {
    //    if (map.get(key) == null) {
    //        map.put(key, 1);
    //    } else {
    //        map.put(key, map.get(key) + 1);
    //    }
    //}